package com.comp5900.impl.huffman;

import java.util.*;
 
public class HuffmanEncoder {

	public static <E> HuffmanTree buildEncodingTree(ArrayList<SymbolFrequencyPair<E>> symbolmap) {
		PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();

		//Initialize the priority queue with leaf nodes containing the symbols and their frequencies
		for (SymbolFrequencyPair<E> p : symbolmap) {
            if (p.frequency > 0){
            	HuffmanLeaf<E> leaf = new HuffmanLeaf<E>(p.frequency, p.value);
            	trees.offer(leaf);
            }
		}

		//Loop until there is only one tree left, the root
		while (trees.size() > 1) {
			/*
			 * Pull the two trees with lowest frequency/priority
			 * and offer a merged parent back into the queue
			 */
			HuffmanTree a = trees.poll();
			HuffmanTree b = trees.poll();
			trees.offer(new HuffmanNode(a, b));
		}

		//Return the root
		return trees.poll();
    }
}
